package com.mlh.backtracking;

import java.util.*;

/**
 * @author 缪林辉
 * @date 2024/4/7 13:59
 * @DESCRIPTION
 */
// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
// 输入：nums = [1,1,2]
// 输出：
// [[1,1,2],
// [1,2,1],
// [2,1,1]]
public class 全排列2 {
    LinkedList<Integer> path=new LinkedList<>();//路径
    List<List<Integer>> res=new ArrayList<>();//最终结果
    boolean[]used;
    //方法一 自己写出
    //利用set集合来去重
    public List<List<Integer>> method1(int[] nums) {
        used=new boolean[nums.length];
        recursion(nums);
        return res;
    }

    public void recursion(int[] nums){
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
        }
        HashSet<Integer>set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(used[i]||set.contains(nums[i])){
                continue;
            }
            set.add(nums[i]);
            used[i]=true;
            path.add(nums[i]);
            recursion(nums);
            used[i]=false;
            path.removeLast();
        }
    }

    //方法二 利用对数值排序来去重
    //这个数值排序去重我思考良久
    //在递归的过程中，其实都是按照数组顺序去不断递归的
    //我之前想一个例子 可以让数组排序去重失效  但是我发现那种情况不可能发生
    //就是因为递归是按照数组顺序来递归的，而不是胡乱递归的
    //因此利用数组排序去重是可以的
    public List<List<Integer>> method2(int[] nums) {
        used=new boolean[nums.length];
        Arrays.sort(nums);
        recursion2(nums);
        return res;
    }

    public void recursion2(int[] nums){
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
        }

        for (int i = 0; i < nums.length; i++) {
            //nums[i]==nums[i-1]&&used[i-1]==false 这里利用数组排序去重
            //used[i-1]==false 是什么意思呢
            //实际上很简单,就是这个数在这层是有的,那些true的数 在上层就被用过了，在这层实际上相当于没有，当然不能用来去重
            if(used[i]||i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            recursion2(nums);
            used[i]=false;
            path.removeLast();
        }
    }

    public List<List<Integer>> practice(int[] nums) {
        Arrays.sort(nums);
        used=new boolean[nums.length];
        recursionPractice(nums);
        return res;
    }

    private void recursionPractice(int[] nums) {
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]||i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            recursionPractice(nums);
            used[i]=false;
            path.removeLast();
        }
    }
}
